AI Answers

1. [45]  Expert System, and related issues

A) [8] Representation
(i) [4]  [Both of the trees below were acceptable.  
The first was more commonly used, the latter slightly better for (1d)]

		MS/AI

      AI-Part		____ware	MTC		Practicum


 222  <other> 223	  142	     156   206		293   390

275  276  226  227

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
		MS/AI

222   AI-Part'  223	____ware	MTC		Practicum


275  276  226  227	  142	     156   206		293   390


(ii) [3] Each leaf node refers to the chore of (taking and passing)
a particular course.
The internal nodes refer to area-wide requirements.
The links represent the subgoal relation.

(iii) [1] It means you have satisfied the requirements needed to graduate.

B) [4] Multiple Parents

(i) [3] Let some course satisfy more than one requirement.
For example, make CS 206 a requirement for the AI part.
(That is, change "I." to now include
	* CS 206.)

(ii) [1] We can no longer call this a "tree".
There are no problems representing this.
Problems might arise in using it, of course: e.g., counting CS206
twice when figuring total units.

C) [15] Complications

(i) [3] It is very difficult: 
First, we'd have to include other classes, to make the 54 units.
Next, consider all the ways of attaining 54 units.
Each of these combinatorially large cases would have to be represented in the tree!
A similar problem would arise when worrying about V.
Multiple copies of each course would have to be included, one for each term the
course is offered.
Only the ones which occurred within two years of the student's enterring date
would be linked into this (by now gargantuan) tree.
The final problem is how to represent the GPA requirement.
We would first have to encode the grade attained for each course in the tree.
Each term the student could only take that set of courses which maintains
his GPA.  This would involve having nodes which each represented a set of courses
offered in the same term.

Clearly this AND-OR tree structure, so nicely suited for I-IV,
is grossly inappropriate for other types of requirements.

(ii) [8] 
This question was asking for a sketch of how to design this ATN.
The description below refers to an ATN which ACCEPTs
a proposed schedule.  We also gave full credit to those who
described ATNS which GENERATED acceptable schedules.

Begin by generating a regular Transition Network for
the core I-IV requirements 
-- this will be similar to the AND/OR tree shown above.
That is, have four nodes in series,
which each (sequentially) examine the proposed schedule.
The j-th node is satisfied if the j-th requirement passes.
(Each of these, in turn, would be a little network,
in basically the obvious fashion.
However, for reasons mentioned below, each OR-junction would have to accept
ALL disjuncts found, not just the first.)
Add on to this another node, OTHER, which could accept any other course.

Now augment this with a few registers.
The CS-Course-Units register would be a counter,
incremented (by the course's units) each time any CS course is passed.
This update is part of the action taken at the end of any
"course pass" node, embedded in any of the first four
top level nodes mentioned above.
Another similar counter, CS-Grade-Points,
would record the  cumulative grade points for these same nodes.
(Like the CS-Course-Units register,
it is updated at the completion of each "primitive" course node.
It value is incremented by the grade received for this course
times the number of units.)
A third Non-CS-Course-Units register would behave like CS-Course-Units,
but only be incremented by the completion of nodes found in OTHER.
A final register, Start-Time, records the time at which you began the program.
(Note these registers are all initiated during the transition leading to
the I node -- to 0 in the first three cases.)

The Start-Time register is needed to handle the "two years requirement", #V:
Associated with each course would be the time at which it was taken;
and only those courses which would be completed 
within two years of that Start-Time register value would only be accepted.

The OTHER node, which accepts any course NOT included anywhere in I-IV,
is needed to deal with the "54 units requirement", #VI.
(Note you have to be a bit careful to insure that each course is counted once and
only once.
This is why each of the first four high level nodes must deal with EVERY
course mentioned in that requirement 
-- in particular, not just the first member of an OR-junction which succeeds.
Suppose someone takes both CS 275 and CS 226, for example.
If the Ith node used only the CS275 course,
the 3 units associated with CS226 would never be counted,
as the I node and the OTHER node would both ignore it.)

All that remains is the final transition, linking that OTHER node with SUCCESS.
Its associated transition test would
i) add together the values of the CS-Course-Units register with the
Non-CS-Course-Units register, and check that the sum was at least 54, and
ii) verify that the ratio of 
CS-Course-Units to CS-Grade-Points (which is the final GPA,) is at least 3.00.

D) [2] Searching
No, αb pruning would not be useful for this example, for two main reasons.
First, it is not defined for this situation.
The "GPA value" at a non-leaf node is NOT simply the
GPA value of a bottom node, which has been propogated up.
Second, the tree is too shallow.

Notes: Many people (incorrectly) argued that αb pruning was
inapplicable because this wasn't an adversarial situation.
One certainly could think of scheduling as trying to maximize your reward.
Second, the fact that the "value" of each leaf node was an ESTIMATE is also
irrelevant.  

E) [9] Heuristics
*  Find nodes which satisfy more than one requirement, and achieve those
	whenever possible.  

-- This is general, refering to the overall structure of the graph.
(Inapplicable to the TREE structure here, but a good idea in general.)

* Take classes which you expect to do well in,
	especially if your current GPA is precariously near the boundary.
-- This is fairly general, refering to a whole class of primitive nodes.
    (each corresponding to a class)

* If there is no penalty for trying to fulfill some requirement and failing,
	then attempt to pass this requirement as often as possible.
-- This is relevant only to a small set of nodes.

* Avoid any classes which require competency in mathematics.
---  Applies to all leaf nodes, potentially pruning away a small percentage of them.

* Try to take as many classes taught by MTC profs as possible.
--- Again, applies to some leaf nodes.

F) [5]  Blackboard Model
NOTE: Many people seemed to equate KS with data.  Wrong.
KS should be viewed as a procedure, one which is triggered by certain types of
input, and uses a particular corpus of facts to generate another hypothesis.
NOTE: Quick overview of the BlackBoard:
Its basic purpose is to store hypotheses.
For this application,
it could house hypothesized schedules, and schedule fragments.
Each fragment stores a set of "What course at what time" assignments.

The abstraction levels roughly parallel the levels of the AND-OR tree.
The bottom "primitive" level are particular time assignments
to the courses themselves;
the higher levels refer to classes of courses 
-- e.g., specifying that some requirement has been satisfied.

One obvious x-axis would represent time in the year
-- when the class is taken (and passed).
This is NOT the same as the time in the week the course is offered;
that is indeed an important consideration, but not appropriate for the x-axis.

One KS could be devoted to detecting schedule conflicts
(it would have access to periodic time schedules).
Another would note when various basic requirements (I-IV) were satisfied.
Another would maintain the GPA (watching especially for times when it begins to
fall around 3.00).
Other KSs could help argue for or against a proposed course,
on the basis of work load for a given term,
how good the teacher is, your personal interest in
the material (esp. for additional courses), misc. constraints such as the
fact that the course is only offered every other year, etc.

G) [6] Other representations
NOTE: Curiously no one used the "obvious" representation for dealing with default
-- units (frames).  
NOTE: Almost everyone wrote out universal statements for those default claims --
what we specifically requested you NOT to do.

i) [4] Default Specification
-------
Production Rules:

IF (AND (Course crs)
	(= (First-Two-Characters crs) CS))
THEN (Department crs CS)

<<above rule is optional -- the important thing is to derive that 
  (Department CS223 CS) >>

IF (Department crs CS))
THEN (TeacherInDept crs CS)

<<Notice that, in most Production Systems, it is not a "contradiction" to
  assert that (TeacherInDept CS223 Physics).>>

-------
Predicate Calculus:

∀ crs. ((Course crs) & (= (First-Two-Characters crs) CS))
	 ⊃   (Department crs CS)

<<above sentence is optional -- the important thing is to derive that 
  (Department CS223 CS) >>

∀ crs, dept. (}[](TeacherInDept crs dept)  & (Department crs CS))
		⊃  (TeacherInDept crs CS)

<<This box, [], is the modal PROVABILITY operator.>>

-------
Units:

CS223
	Isa:	CS-Course

CS-Course
  TeacherInDept: CS

<<Here any individual instance of CS-Course, such as CS223, could still override
  this specification -- if its TeachInDept value was, say, Physics.>>

ii) New defaults
-------
Production Rules:

IF (Department crs CS))
THEN (Note (TeacherInDept crs CS))

<<Again, this is not "contradicted" by assertions like
  (TeacherInDept CS223 CS).>>

-------
Predicate Calculus:

∀ crs, dept. (}[](TeacherInDept crs dept)  & (Department crs CS))
		⊃  (NOT (TeacherInDept crs CS))

-------
Units:

CS223
	Isa:	CS-Course

CS-Course
  TeacherInDept: x
	DefaultCondition:	(NOT (EQ x CS))

<<There are many other equally-terse solutions using units.>>

2. [15] AI Philosophy/Methods

A) [5] AI's Contribution to Psychology
AI research offers a language (information processing
language of computer processes) and a set of concepts applicable to the
study of human information processing. The most fundamental modeling
assumption is that human thought can be reduced (in the scientific
useage of that term) to a set of elementary information processing
operations. A computer is appropriate because: since a computer is
a general symbol processing system, any symbol-system model that can
be conceived can be given an operational instantiation and rigorous test.
AI has also lead to rich source of metaphors for describing people.

B) [3] Psychology's Contribution to AI
Essentially no progress is attributable to such brain modeling.
The only example that may be at all relevant is in vision,
where much of the low-level processing (at the sensor level, or slightly
above) parallels the human visual system.

NOTE: Many people answered a different question here -- addressing the 
issue of how people have been described, using the metaphor of computers.
This was not what we asked about.

C) [4] Dendral's Contribution to AI
Its main contribution 
(in addition to its value as an existance proof that expert systems were possible)
was the discovery that what was primarily
responsible for the high levels of competence in performance was the
knowledge that the program contained rather than the power of its
inference methods. DENDRAL had little to say to the science of
human behavior other than the result mentioned in the last sentence (which
in itself is an important result for psychologists and educational
psychologists).

D) [3] Dendral's Design Goals
If DENDRAL had sought to be a contribution to psychology, then
a much more careful method of studying exactly how each expert chemist
solved each problem would have to have been employed; with careful
methods of acquiring and analyzing data invented or adapted. 
Also, there would have to have been a detailed match of the behavior of
program and human.